home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / icon / newsgrp / group99a.txt / 000207_icon-group-sender _Mon Oct 4 12:38:36 1999.msg < prev    next >
Internet Message Format  |  2000-09-20  |  2KB
  1. Return-Path: <icon-group-sender>
  2. Received: (from root@localhost)
  3.     by baskerville.CS.Arizona.EDU (8.9.1a/8.9.1) id MAA09976
  4.     for icon-group-addresses; Mon, 4 Oct 1999 12:38:02 -0700 (MST)
  5. Message-Id: <199910041938.MAA09976@baskerville.CS.Arizona.EDU>
  6. From: eka@corp.cirrus.com (Eka Laiman)
  7. Subject: Re: A small puzzle
  8. To: sbw@tapestry.tucson.az.us (Steve Wampler)
  9. Date: Mon, 4 Oct 1999 10:49:38 -0700 (PDT)
  10. Cc: icon-group@optima.CS.Arizona.EDU
  11. Errors-To: icon-group-errors@optima.CS.Arizona.EDU
  12. Status: RO
  13.  
  14. > I haven't posted anything for a while, but thought this might be fun:
  15. > 
  16. >    Write an Icon program to generate the pairings in a round-robin
  17. >    tournament.  The program should accept the player names as
  18. >    command line arguments (see the example below).
  19. > 
  20. > In a round-robin tournament, every player plays every other player
  21. > exactly once.  If there are an odd number of players, then a
  22. > special "bye" player is added.
  23. > ................. edited ..................
  24.  
  25. If I understand the problem correctly, here is how I approach the
  26. problem:
  27.  
  28. Model the problem as "graph" in the following sense:
  29.  
  30.     Each player forms a vertex of the graph. Each pair of player
  31.     is an edge in the graph.
  32.  
  33. >From the condition that every player plays every other player exactly
  34. once, we see the following graph property: each vertex is connected
  35. to every vertex in the graph, forming a "complete graph".
  36.  
  37. Let N be the number of the vertices in the graph, clearly there are
  38.     N(N-1)/2
  39. edges.
  40.  
  41. >From this analysis we come up with the following algorithm:
  42.  
  43.     Let player[1..n] be the array of the players.
  44.  
  45.     1.  Set up the second array partner[1..n] such that:
  46.         partner[i] := player[n - i + 1]
  47.         # initialize partner as the reverse of player.
  48.     2.  Repeat the following steps (n - 1) times:
  49.         2a. For i := 1 to n/2 do
  50.         write(pair(player[i], partner[i])
  51.     2b. Rotate array partner one step.
  52.  
  53. >From the rule of counting, we see that step 2 generates all edges
  54. in our complete graph.
  55.  
  56. I think the implementation of the above algorithm is straightforward.
  57.  
  58. -eka-
  59.